package 算法.leetcode.labuladong.二叉树;

import 算法.leetcode.offer.base.TreeNode;

/**
 * @author lchenglong
 * @date 2022/6/24
 */
public class 二叉树中的最大路径和 {
    class Solution {
        int ans=Integer.MIN_VALUE;
        public int maxPathSum(TreeNode root) {
            if (root == null) return 0;
            // 计算单边最大路径
            oneSidePath(root);
            // 返回最大值
            return ans;
        }
        // 计算从根节点 root 为起点的最大单边路径和
        public int oneSidePath(TreeNode root){
            if (root == null)return 0;
            // 计算左右子树的最大单边路径和,如果小于0 则用0替代
            int l = Math.max(0,oneSidePath(root.left));
            int r = Math.max(0,oneSidePath(root.right));
            // 后序遍历位置，顺便更新最大路径和
            int maxPath = l + r + root.val;
            ans = Math.max(ans,maxPath);
            // 实现函数定义，左右子树的最大单边路径和加上根节点的值
            // 就是从根节点 root 为起点的最大单边路径和
            return Math.max(l,r)+ root.val;
        }
    }

}
